//
//  Problem95.swift
//  TestProject
//
//  Created by 武侠 on 2021/2/26.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit
/*
 95. 不同的二叉搜索树 II
 给定一个整数 n，生成所有由 1 ... n 为节点所组成的 二叉搜索树 。

 示例：
 输入：3
 输出：
 [
   [1,null,3,2],
   [3,2,null,1],
   [3,1,null,null,2],
   [2,1,3],
   [1,null,2,null,3]
 ]
 解释：
 以上的输出对应以下 5 种不同结构的二叉搜索树：

    1         3     3      2      1
     \       /     /      / \      \
      3     2     1      1   3      2
     /     /       \                 \
    2     1         2                 3
  
 提示：
 0 <= n <= 8
 */

public class TreeNode {
    public var val: Int
    public var left: TreeNode?
    public var right: TreeNode?
    public init() { self.val = 0; self.left = nil; self.right = nil; }
    public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
    public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
        self.val = val
        self.left = left
        self.right = right
    }
}
@objcMembers class Problem95: NSObject {
    func solution() {
        let arr = generateTrees(3)
        print(arr.count)
        for node in arr {
            print(printNodeTree(node))
        }
    }
    
    /*
     动态规划
     1: 创建一个二维数组 dp[len][len]
     2: dp[i][j] i～j的二叉搜索树数组[TreeNode?]
     3: dp[i][j] = 和（）
        (i) + dp[i+1][j]
        dp[i][i] + (i+1) + dp[i+2][j]
        dp[i][i+1] + (i+2) + dp[i+3][j]
        ......
        dp[i][j-2] + (j-1) + dp[j][j]
        dp[j][j-1] + (j)
     */
    func generateTrees(_ n: Int) -> [TreeNode?] {
        if n == 0 {
            return []
        } else if n == 1 {
            return [TreeNode(1)]
        }
        
        var dp = Array(repeating: Array(repeating: Array<TreeNode?>(), count: n+1), count: n+1)
        var i = n
        while i >= 0 {
            for j in i...n {
                if i==j {
                    dp[i][j] = [TreeNode(i)]
                } else {
                    var nodes: [TreeNode?] = []
                    for k in i...j {
                        if k == i {
                            for sNode in dp[i+1][j] {
                                let kNode:TreeNode? = TreeNode(k)
                                kNode?.right = sNode
                                nodes.append(kNode)
                            }
                        } else if k == j {
                            for sNode in dp[i][j-1] {
                                let kNode:TreeNode? = TreeNode(k)
                                kNode?.left = sNode
                                nodes.append(kNode)
                            }
                        } else {
                            for leftNode in dp[i][k-1] {
                                for rightNode in dp[k+1][j] {
                                    let kNode:TreeNode? = TreeNode(k)
                                    kNode?.left = leftNode
                                    kNode?.right = rightNode
                                    nodes.append(kNode)
                                }
                            }
                        }
                    }
                    dp[i][j] = nodes
                }
//                print(i, j)
//                printNodeTrees(dp[i][j])
            }
            i -= 1
        }
        
        return dp[1].last ?? []
    }
    
}

func printNodeTrees(_ nodes: [TreeNode?]) {
    for node in nodes {
        print(printNodeTree(node))
    }
}

func printNodeTree(_ node: TreeNode?) -> String {
    guard let safeNode = node else {
        return "null, "
    }
    
    if safeNode.left == nil, safeNode.right == nil {
        return "\(safeNode.val), "
    } else {
        return "\(safeNode.val), " + printNodeTree(safeNode.left) + printNodeTree(safeNode.right)
    }
}
